The present invention is directed to digital signal receivers and in particular to receivers that employ maximum-likelihood-sequence estimation.
Maximum-likelihood-sequence estimation (MLSE) is a method widely employed to extract, from corrupted signals, the symbols that the signals had been intended to carry. The principle of the MLSE algorithm--on which the present invention is based--was described in Forney, "Maximum-Likelihood Sequence Estimation of Digital Sequences in the Presence of Intersymbol Interference," IEEE Trans. Infor. Theory, vol. IT-18, May 1972. For purposes of exposition, however, we will describe an embodiment in connection with a particular application, namely, .pi./4-shifted differential-quadrature phase-shift-keying (.pi./4-DQPSK) transmission, which has been proposed for digital transmission using cellular telephones.
In such an arrangement, an audio signal picked up by a microphone 10 is applied to transmitter front-end circuitry 12, which digitizes the analog signal, performs various levels of encoding and framing of the resultant raw digitized signal, and produces a resultant output as a stream of bits. A .pi./4-DQPSK modulator 14 receives the resultant sequence two bits at a time and responds to each bit pair by generating a two-component output signal x(n), which specifies one of eight points equally spaced about a circle in the complex plane, the phase of each point representing a different phase with respect to a carrier. Each of the four possible two-bit combinations results in a different one of the four possible shifts from the previous phase: .+-..pi./4 and .+-.3.pi./4. Accordingly, the .pi./4-DQPSK-modulator output depends not only on its current two-bit input but also on its previous output, as the constellation diagram of FIG. 2 shows.
That diagram shows that, if the symbol generated at a given time represents, say, a phase angle of zero, the subsequent symbol can represent only an odd multiple of .pi./4. The same is true of all of the even multiples of .pi./4. If the phase that results from one bit pair in the bit stream point is an even multiple of .pi./4, therefore, the phase that results from the bit pair that follows it will be an odd multiple thereof, and vice versa.
As FIG. 1 shows, modulators 16 and 18 amplitude modulate in-phase and quadrature components, respectively, of a carrier that a source 20 generates. However, if the raw output of the .pi./4-shifted-DQPSK modulator 14 were applied directly to the amplitude modulators 16 and 18, the abrupt phase changes would cause the spectrum of the resultant signal to be much wider than is allowed for single-channel cellular-telephone transmission. Digital filters 22 and 24 therefore subject the two DQPSK-modulator outputs to low-pass filtering before the resultant signals are used to modulate the two carrier components. An analog adder 26 then sums the outputs of modulators 16 and 18 to produce a DQPSK signal, which an amplifier 28 boosts in power before transmitting it by way of an antenna 30.
The antenna may be thought of as delivering the signal to the relatively uncontrollable, time-varying part 32 of the signal channel. This part of the channel usually includes multiple different-length paths from the transmitter to the receiver, and these paths typically fade and change as the transmitter and/or receiver moves about.
At the receiver end, an antenna 33 picks up the signal and applies it to a down-converter 34, which extracts the in-phase and quadrature components and generates a two-component baseband output signal y(t). A sampler 35 samples the (complex-valued) signal y(t) to produce a sequence of samples, each of which may, for instance, take the form of two eight-bit components respectively representing the relative amplitudes of the in-phase and quadrature components.
Matched filters 36 and 37 respectively filter the in-phase and quadrature components of y(t). In the preferred embodiment the responses of filters 36 and 37 are the same as those of pulse-shaping filters 22 and 24, and the concatenation of each pulse-shaping filter with its corresponding matched filter forms a respective Nyquist filter, i.e., a filter whose impulse response goes through zero at t=nT, n=1,2, . . . , where T, the symbol period, is 41.2 .mu.sec in the North American digital cellular system. In the absence of channel segment 32, therefore, the output of the Nyquist filter at nT would exhibit no intersymbol-interference (ISI) distortion. However, due to the multipath characteristic of the radio-channel part 32 and receiver noise, ISI distortion and noise corruption do occur. To combat distortion and extract the desired information, therefore, an MLSE circuit 38 processes y(n) to arrive at an estimate x'(n) of the symbols x(n) originally produced. Further processing 39 then typically decodes this symbol train and performs other functions before producing the ultimate signal applied, say, to a handset receiver 40.
FIG. 3 is a block diagram of the maximum-likelihood sequence estimator 38. A symbol-sequence-derivation circuit 42 receives a (filtered) sample sequence y(n) from the matched filters and determines, typically by employing the Viterbi algorithm in a manner that will be described shortly, the sequence of symbols x'(n) most likely to have resulted in the sample sequence y(n) that the MLSE circuitry receives from the receiver's front-end circuitry. FIG. 3 shows the resultant symbol sequence as x'(n-N) to reflect the processing delay of N symbol periods between reception of a sample y(n) and generation of the corresponding derived symbol x'(n).
To derive these symbols x'(n-N), the symbol-sequence-derivation circuit 42 requires parameters that characterize the time-varying channel segment 32. The determination of these parameters is the task of the channel-impulse-response estimator 44, which includes a transversal filter 46 depicted in FIG. 4. Filter 46 models channel segment 32, or, more precisely, models the effect that the time-varying channel segment 32 has as a constituent of the larger channel that extends from the DQPSK modulator output port to the output ports of the matched filters 36 and 37. The derived symbols x'(n-N) are assumed, for the purposes of estimator 44, to be precisely the symbols that the DQPSK modulator initially produced: they were the actual inputs to the channel whose departures from the ideal the filter 46 is intended to model. In many practical systems, the operation may be initialized with application of a sequence known to be sent during initialization, as switch 47 of FIG. 3 suggests. Indeed, in certain systems in which certain predetermined "header" sequences are transmitted on a regular basis, the model may be updated only during the header sequence, and the predetermined training sequence is used as the estimator's only reference sequence, to the exclusion of the derived symbols. In such an arrangement, of course, the model is updated only during header transmission.
The filter 46 includes a number of delay elements 48, each of which imposes a delay equal to one symbol period T. Respective multipliers 50 multiply the delay-element contents by respective coefficients f.sub.0, f.sub.1, . . . , f.sub.L, which will collectively be referred to as a vector F of channel-model parameters. A summing circuit 52 adds the results together to generate the filter output y'(n-N), which is the result of applying the original symbols to the channel model.
A subtraction circuit 54 subtracts this model output y'(n-N) from an N-delayed version y(n-N) of the actual channel output that a delay circuit 55 generates, and the difference is the error e(n-N) in the model output. An update circuit 56 uses this error to adjust the values of the channel-model parameters F in accordance with one of the known error-reducing methods. The equation depicted in block 56 represents the least-mean-square adaptation algorithm, although many others, such as the recursive-least-square algorithm, could be employed instead.
In short, a new set F(n-N) of channel parameters is calculated at each symbol time n, and each updated version of the channel parameters F(n-N-1) is employed, in a manner that will now be described, to incorporate a new sample y(n) into the derivation of the sequence of derived symbols x'(n).
In principle, the general approach is to apply, to the model characterized by channel parameters F, all permissible sequences x"(n) that the DQPSK modulator 14 could have generated and to determine which one of the resultant trial output sequences y"(n) is "closest" by some measure to the observed actual sample train y(n).
In practice, this determination is ordinarily performed by means of the Viterbi algorithm, which is conventionally illustrated by a trellis diagram such as FIG. 5A. The trellis diagram of FIG. 5A includes an array of nodes, each of which represents the "state" of channel segment 32 at a given symbol time. More specifically, each row represents a different "state," while each column represents a different symbol time.
The state of a channel can be thought of as representing the last L symbols that have been applied to it at any particular time, where the channel's memory length is L symbol periods. As those skilled in the art will recognize, the only input upon which the output of a memoryless channel depends is the current one. For a channel that has memory, as channel segment 32 is assumed to have, the output depends not only on the current symbol but on the sequence of L previous symbols.
Each row in FIG. 5A therefore represents a different permissible sequence of L symbols and, equivalently, a different state into which a corresponding sequence of L symbols would have placed the channel segment 32. Moreover, each line ("branch") leading to the right from a given node in one column to a different node in the next column represents a different one of the permissible symbols applied to the channel in the state that the given node represents. In a trellis diagram that represents all possible sequences of states, therefore, the number of branches leading to the right from any given node is equal to the number of permissible symbols at the corresponding symbol time.
Additionally, each left-to-right path through the trellis represents a sequence of states and thus a sequence of code symbols. For instance, path 60 of FIG. 5B represents the code-symbol-sequence AHAB, while each of the path's constituent branches 62, 64, and 66 represents a symbol.
Now, in the particular trellis diagram of FIG. 5A, it is assumed that L=1, so the number of states is equal only to the number of permissible symbols at any symbol time. Moreover, since the trellis diagram of FIG. 5A represents the .pi./4-shifted-DPSK coding scheme assumed here, there are only four nodes in each column, one for each permissible symbol. Again because L=1 and the number of states in each column is thus equal to the number of permissible symbols at the corresponding symbol time, each node in a given column--that is, each state--can be reached from any node/state in the previous column.
As was stated above, the purpose of an MLSE scheme is to find, among all permissible sequences, the one most likely to have resulted in the input sample train of y(n)'s that was actually observed. Determination of the various sequences' probabilities is based on the assumption that the model produced by the channel-impulse-response estimator 44 is exact but that the y(n)'s result from the addition of Gaussian noise to that model's output.
Under this assumption, the probability that a given sample y(n) resulted from a given sequence is a function of the difference between that sample y(n) and the output y"(n) that the model produces when that sequence is applied to it as an input. That is, the probability density is proportional to exp[-(1/2).vertline.y-y".vertline..sup.2 /.sigma..sup.2 ], where .sigma. is the standard deviation of the noise distribution. If this quantity is computed for each symbol in a candidate sequence, then the product of those quantities is proportional to the likelihood that the candidate sequence was the one applied to the pulse-shaping filters 22 and 24 to result in the sequence of samples y(n) that was actually observed.
The computational complexity of computing the likelihood is reduced by replacing multiplications of the probability density with additions of quantities proportional to their logarithms. That is, a "branch metric" proportional to .vertline.y-y".vertline..sup.2 is computed for each symbol in the sequence (or, as it is more commonly described in this context, for each state transition in the sequence), and the branch metrics for all of the state transitions of a sequence are added together. Clearly, the sequence whose path metric--i.e., whose sum of constituent branch metrics--is the lowest is the one with the maximum likelihood.
By (again, in principle) comparing those path metrics for all permissible sequences, the MLSE scheme determines the sequence most likely to have been sent. However, rather than computing, for a sequence of M received samples y(n), the path metrics for all of the 4.sup.M permissible sequences that could have caused it, the Viterbi algorithm obtains essentially the same result with much fewer calculations, as we will now demonstrate.
We join the operation of the Viterbi algorithm at time n, when a new sample y(n) has just been taken. At this point, it is known only that the symbol sent at time n is one of the legal symbols B, D, F, and H, but no decision has been made concerning which of the four it was. Indeed, the algorithm has not yet determined which of the legal symbols A, C, E, and G was sent at the previous symbol time n-1. In a manner that will shortly be described, however, the algorithm has determined, for each of the state-representing nodes in column n-1, the path by which that node was reached if it does represent the state that actually prevailed at time n-1.
FIG. 5C depicts the paths respectively associated with the four nodes in column n-1; i.e., it omits the FIG. 5A branches that do not belong to any of those paths. When incoming sample y(n) is initially taken, the Viterbi algorithm has not yet determined which path corresponds to each of the nodes in column n. In the illustrated system, therefore, sixteen candidate paths are still possible at that time--that is, each of the four legal states at time n could have been preceded by any of the four states that were legal at time n-1. For the state resulting from transmission of symbol D, for instance, the four paths respectively including branches 68, 70, 72, and 74 all represent candidates for the sequence that ended in that state at time n.
To determine which of these paths to assign to each state at time n, the receiver employs an apparatus of the type depicted in FIG. 6. (As those skilled in the art will recognize, FIG. 6 is a functional diagram, in which the blocks represent different functions that may actually be provided by common circuitry, such as a common digital signal processor or microprocessor and related memory.) A path-information memory 76 contains information concerning which symbol sequences are legal. From this information, a data generator 78 generates and applies to a weighting-function circuit 80 series of vectors X" representing the different candidate paths.
One vector, for instance, would represent two states on path 82 of FIG. 5C. It would thus be [exp(j.pi.), exp(j3.pi./4)], i.e., the values of the (one-symbol) sequence E that defines that path's state at time n-1 and of the symbol D hypothetically transmitted. The weighting-function step 80 computes the scalar product of this vector and the channel parameters F and thereby determines the value y"(n) that the actual sampled value y(n) would have had if the sequence represented by path 82 had actually been transmitted, the current channel parameters F modeled the channel precisely, and no noise had been present.
A subtraction circuit 84 computes the difference between this value and the actually sampled value y(n). A metric-update element 86 computes from this difference the branch metric associated with branch 72 (the last branch in path 82), typically by squaring its magnitude, and it adds the result to an old path metric retrieved from an old-surviving-path-metric memory 88. The old path metric had been computed in previous iterations by adding up the branch metrics of path 82's other constituent branches.
The path metrics for all of the other branches that lead to node 90 (FIG. 5C) are similarly computed, and the metric-update circuit 86 determines which of these path metrics is the lowest. The path thus identified is then considered to represent the symbol sequence that is most likely to have been transmitted if the last state is the one that node 90 represents. This path is denoted a "surviving path," and its metric is stored in new-surviving-path-metric memory 92.
The same procedure is followed for each of the other nodes in column D, and the contents of memory 92 are then transferred to memory 88 for the next iteration. FIG. 5D depicts a typical result.
The path-metric results can be employed in a number of ways to arrive at the derived symbol sequence. Assume, for instance, that time n is the end of transmission and that the symbol sequence does not need to be known until that time. In such a situation, the four path metrics for the paths ending at each node in column n are compared, and the derived symbol-sequence output is simply that which corresponds to the path having the lowest path metric.
Even if the ultimate user does not need the sequence until the end of transmission, however, derived symbols may be needed earlier than that to update the channel model. In such a situation, "tentative" decisions of the symbol sequences may be made earlier and applied to the channel-impulse-response estimator 44 so as to keep the channel model current. This may result in an input sequence to the channel-impulse-response estimator that differs slightly from the output presented to the user.
It may also happen that part of the maximum-likelihood sequence will be apparent before the end of the transmission. In FIG. 5D, for instance, it is clear that, regardless of which path ultimately turns out to represent the maximum-likelihood sequence, it will include the path by which state A was reached at time n-3. Thus, some of the symbols in the maximum-likelihood sequence, as computed at the end of transmission, can be known and presented to the user before transmission ends.
In most situations, of course, the user will need some output before transmission ends, and the output in those situations is what would otherwise be a tentative sequence.
This MLSE method is a powerful tool for extracting transmitted symbols from a signal that has been distorted by the channel through which it has propagated and corrupted by noise, and it has accordingly found favor as a way of dealing with the difficulties that are encountered in some communications systems. The requirements presented by time-division multiplexing in narrow-band cellular-telephone channels are quite severe, however, and an improvement over the performance that results even from conventional MLSE techniques would be welcome.